COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00011 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a61 tex[154,phy] \today\hfill}

\parskip 5pt
\line{\bf Primitive Recursion\hfil}

\medskip
Let $\pi$, $\alpha$, $\beta$ be any fixed functions for which
$$\eqalign{&\pi\hbox{: }{\bf N}\times {\bf N}→{\bf N}+1\cr
&\alpha\bigl(\pi(x,y)\bigr)=x\cr
&\beta\bigl(\pi(x,y)\bigr)=y\cr}$$
so that $\pi(x↓1,y↓1)=\pi(x↓2,y↓2)$ implies $x↓1=x↓2$, $y↓1=y↓2$. We call $\pi$
a {\sl pairing function\/}, $\alpha$~and $\beta$ the {\sl projections\/}
of~$\pi$. 
We use $X↑{(n)}$ as an abbreviation for $x↓1,x↓2,\ldots,x↓n$.
Define $\langle\,\rangle =0$, $\langle x↓1,\ldots,x↓n\rangle =
\pi(x↓1,\langle x↓2,\ldots,x↓n\rangle)≠0$. Then
$$\eqalign{\alpha(\langle X↑{(n)}\rangle)&=x↓1\cr
\beta(\langle X↑{(n)}\rangle)&=\langle x↓2,x↓3,\ldots,x↓n\rangle\cr
\beta↓i(\langle X↑{(n)}\rangle)=\beta↑{(i-1)}(\langle X↑{(n)}\rangle)
&=\langle x↓i,x↓{i+1},\ldots,x↓n\rangle\cr
\alpha↓i(\langle X↑{(n)}\rangle)=\alpha\bigl(\beta↑{(i-1)}(\langle X↑{(n)}\rangle)
\bigr)&=x↓i\,.\cr}$$

\display 20pt:$\bullet$:
$Z(\,)=0$ is a primitive recursive function; $Z$: ${\bf N}↑0→{\bf N}$.

\smallskip
\display 20pt:$\bullet$:
$S(x)=x+1$, the {\sl successor\/} function, is primitive recursive;
$S$: $N↑1→N$.

\smallskip
\display 20pt:$\bullet$:
$P↓{i,n}(X↑{(n)})=x↓i$, a {\sl projection function}, is primitive recursive
for each $1≤i≤n$; $P↓{i,n}$: $N↑n→N$.

\smallskip
\display 20pt:$\bullet$:
If $g↓1,g↓2,\ldots,g↓a$ ($a≥0$) are primitive recursive functions from
$N↑0$ to~$N$, ($b≥0$), and $f$: $N↑a→N$ is primitive recursive, then
$h={\rm Comp}(f; g↓1,g↓2,\ldots,g↓a)$: $N↑b→N$ is primitive recursive;
$$h(X↑{(a)})=f\bigl(g↓1(X↑{(a)}),g↓2(X↑{(b)}),\ldots,g↓a(X↑{(b)})\bigr)\,.$$

\smallskip
\display 20pt:$\bullet$:
The pairing function $\pi$ and its projections $\alpha$ and $\beta$:
$N→N$ are primitive recursive.

\smallskip
\display 20pt:$\bullet$:
If $f$: $N→N$ is primitive recursive, then $f↑{\ast}(x,y)=f↑{(x)}(y)$: $N↑2→N$
is primitive recursive.

\smallskip
\display 20pt:$\bullet$:
The primitive recursive functions are the least class satisfying the above.

\smallskip
Taking $f=Z$, $a=0$, in the definition of composition gives $h(X↑{(a)})=0$,
a~primitive recursive function for any $a≥0$.

Taking $f=S$ in the definition of $f↑{\ast}$ gives $S↑{\ast}(x,y)=S↑{(x)}(y)
=x+y$ primitive recursive.

If we write $h(X↑{(n)})=f↓1\bigl(x↓i,x↓j,f↓2(x↓k,x↓l)\bigr)$, say, where $i$, $j$,
$k$, and~$l$ are constants between 1 and~$n$, and $f↓1$, $f↓2$ are primitive
recursive, we can rewrite the definition as
$$\eqalign{g(X↑{(n)})&=f↓2\bigl(P↓{k,n}(X↑{(n)}),P↓{l,n}(X↑{(n)})\bigr)\cr
h(X↑{(n)})&=f↓1\bigl(P↓{i,n}(X↑{(n)}),P↓{j,n}(X↑{(n)}),g(X↑n)\bigr)\cr}$$
to show that $g$ and $h$ are primitive recursive. Henceforth we use this 
technique tacitly, building expressions from components of $X↑{(n)}$
and known primitive recursive functions, including~0. For example,
$$h(x↓1,x↓2)=x↓1+2=S\bigl(S(x↓1)\bigr)=S\bigl(S\bigl(P↓{12}(X↑{(2)})\bigr)\bigr)$$
is primitive recursive.

If $g↓1,g↓2,\ldots,g↓a$ are p.r., the function $G$ that maps
$\langle X↑{(b)}\rangle$ into $\langle g↓1(X↑{(b)}),g↓2(X↑{(b)}),\ldots,
g↓a(X↑{(b)})\rangle$ is p.r.; if $y=\langle X↑{(b)}\rangle$, $x↓1=\alpha(y)$,
$x↓2=\alpha\bigl(\beta(y)\bigr)$, $x↓3=\alpha\bigl(\beta\bigl(\beta(y)\bigr)\bigr)$,
$x↓i=\alpha↓i(y)$, etc.,\break
$g↓i(X↑{(b)})=g↓i\bigl(\alpha↓1(y),\alpha↓2(y),\ldots\,\bigr)$,
$\langle g↓1(X↑{(b)}),\ldots,g↓a(X↑{(b)})\rangle
=\pi\bigl(g↓1\bigl(\alpha↓1(y),
\alpha↓2(y),\ldots\,\bigr),\pi\bigl(g↓2(\ldots)$,\break
$\ldots,\pi\bigl(g↓a(\ldots),0
\bigr)\bigr)\bigr)\ldots\bigr)$
so $G(y)=$ the above expression formed by compositon from known p.r.\
 functions. Then $G↑{\ast}(k,\langle X↑{(b)}
\rangle)$ performs the above mapping on $\langle X↑{(b)}\rangle$, $k$~times,
and is a primitive recursive function of $k$, $X↑{(b)}$.

The predecessor function $x\dminus 1$, which is 0 if $x=0$, $x-1$ if $x>0$,
can easily be shown p.r.\ now. Let $G$ map $\langle u,v\rangle$ into
$\langle 1,v+u\rangle$. Then
$$\eqalign{&\hbox{$G↑{(0)}$ maps $\langle 0,0\rangle$ into $\langle 0,0\rangle$};\cr
&\hbox{$G↑{(1)}$ maps $\langle 0,0\rangle$ into $\langle 1,0\rangle$};\cr
&\hbox{$G↑{(x)}$ maps $\langle 1,0\rangle$ into $\langle 1,x\rangle$};\cr
&\hbox{$G↑{(1+x)}$ maps $\langle 0,0\rangle$ into $\langle 1,x\rangle$};\cr
&x\dminus 1=\alpha↓2\bigl(G↑{\ast}(x,\langle 0,0\rangle)\bigr)\,.\cr}$$
To show that multiplication is p.r., let $G$ map $\langle u,v\rangle$
into $\langle u,v+u\rangle$; then $G↑{(x)}$ maps $\langle u,0\rangle$ into
$\langle u,xu\rangle$, and $xu=\alpha↓2\bigl(G↑{\ast}(x,\langle u,0\rangle
)\bigr)$.

The number $g(n)$ of $i<n$ for which $f(i)=0$ is p.r.\ if $f$ is;
let $G$ map $\langle u,v\rangle$ into 
$\langle u+1,v+\bigl(1\dminus f(u)\bigr)\rangle$. 
Then $G↑{(n)}$ maps $\langle 0,0\rangle$ into $\langle n,g(n)\rangle$;
details are trivial.

Anything computable in {\tt ALGOL/PASCAL/FORTRAN} using only known p.r.\ functions,
assignment, conditional statements, {\tt FOR/DO} statements, and compound
statements is primitive recursive. Allowing {\tt WHILE}, however, gets to
computable functions that are not p.r.


\bigskip
\parindent0pt
\copyright 1987 Robert W. Floyd.
First draft (not published)
September 4, 1987.
%revised date;
%subsequently revised.

\bye